// #include <stdio.h>
// #include <stdbool.h>
// #include"windows.h"
//
// #define MAX_SIZE 100 // 顺序表的最大容量
//
// // 顺序表结构体
// typedef struct {
//     int data[MAX_SIZE]; // 数据存储数组
//     int length;         // 当前顺序表长度
// } SeqList;
//
// // 初始化顺序表
// void InitSeqList(SeqList* L) {
//     L->length = 0; // 初始长度为 0
// }
//
// // 向顺序表中插入元素
// bool Insert(SeqList* L, int index, int value) {
//     if (index < 0 || index > L->length || L->length >= MAX_SIZE) {
//         printf("插入位置不合法或顺序表已满！\n");
//         return false;
//     }
//     for (int i = L->length; i > index; i--) {
//         L->data[i] = L->data[i - 1]; // 元素后移
//     }
//     L->data[index] = value; // 插入新元素
//     L->length++; // 长度加 1
//     return true;
// }
//
// // 折半查找非递归
// int BinarySearch(SeqList* L, int target) {
//     int left = 0;              // 左边界
//     int right = L->length - 1; // 右边界
//
//     while (left <= right) {
//         int mid = left + (right - left) / 2; // 计算中间位置
//         if (L->data[mid] == target) {
//             return mid; // 找到目标，返回索引
//         } else if (L->data[mid] < target) {
//             left = mid + 1; // 目标在右半部分
//         } else {
//             right = mid - 1; // 目标在左半部分
//         }
//     }
//     return -1; // 未找到目标，返回 -1
// }
//
// // 折半查找非递归
// int BinarySearchDiGui(SeqList* L,int target,int left,int right) {
//     if(left>right) {
//         return -1;
//     }
//     int mid=(left+right)/2;
//     if(L->data[mid]==target) {
//         return mid;
//     }else if(target<L->data[mid]) {
//         return BinarySearchDiGui(L,target,left,mid-1);
//     }else {
//         return BinarySearchDiGui(L,target,mid+1,right);
//     }
// }
//
// int main() {
//     SetConsoleOutputCP(CP_UTF8);
//     SeqList L;
//     InitSeqList(&L);
//
//     // 向顺序表中插入有序元素
//     Insert(&L, 0, 1);
//     Insert(&L, 1, 2);
//     Insert(&L, 2, 3);
//     Insert(&L, 3, 5);
//     Insert(&L, 4, 8);
//     Insert(&L, 5, 9);
//     Insert(&L, 6, 10);
//
//     int target = 8; // 查找目标
//
//     // 调用折半查找函数
//     int index = BinarySearch(&L, target);
//
//     // 输出结果
//     if (index != -1) {
//         printf("目标 %d 在顺序表中的索引是: %d\n", target, index);
//     } else {
//         printf("目标 %d 未找到！\n", target);
//     }
//
//     //递归折半查找
//     int index2=BinarySearchDiGui(&L,target,0,L.length-1);
//     // 输出结果
//     if (index2 != -1) {
//         printf("目标 %d 在顺序表中的索引是: %d\n", target, index2);
//     } else {
//         printf("目标 %d 未找到！\n", target);
//     }
//     return 0;
// }